// Created by WXX on 2021/9/26 9:21
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define x first
#define y second

class Solution {
public:

    typedef pair<int, int> PII;

    int shortestPathBinaryMatrix(vector<vector<int>> &grid) {

        if (grid[0][0] == 1) return -1;

        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> st(n, vector<bool>(m));
        vector<vector<int>> dist(n, vector<int>(m));
        queue<PII> q;
        q.push({0, 0});
        dist[0][0] = 1;
        st[0][0] = true;
        while (q.size()) {
            auto t = q.front();
            q.pop();

            if (t.x == n - 1 && t.y == m - 1) return dist[n - 1][m - 1];

            for (int i = -1; i <= 1; i++)
                for (int j = -1; j <= 1; j++) {
                    if (i == 0 && j == 0) continue;
                    int x = t.x + i, y = t.y + j;
                    if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0 && !st[x][y]) {
                        st[x][y] = true;
                        dist[x][y] = dist[t.x][t.y] + 1;
                        q.push({x, y});
                    }
                }
        }

        return -1;
    }
};

int main() {

    vector<vector<int>> grid = {{0, 0, 0},
                                {1, 1, 0},
                                {1, 1, 0}};
    cout << Solution().shortestPathBinaryMatrix(grid) << endl;  // 4

    return 0;
}
